\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}
	
	\textbf{题目大意}
	
	\begin{quote}
		给定一个长度为 \(N\) 的序列 \(A\) 和一个常数 \(K\)
		
		有 \(M\) 次询问
		
		每次询问查询一个区间 \([L , R]\) 内所有数最少分成多少个连续段
		
		使得每段的和都 \(<= K\) ，若无解则输出 "\(Chtholly\)"
	\end{quote}
	
	\textbf{解题思路}
	
	\begin{quote}
		简单回忆一下倍增求 \(LCA\) 思想：
		
		\begin{itemize}
			\item
			\(f[i][j]\) 表示以 \(i\) 为起点，往上跳 \(i + 2^j\) 步后得到的祖先
			\item
			因为往上跳 \(2^j\) 等价于先往上跳 \(2^{j - 1}\) 步后再往上跳
			\(2^{j - 1}\) 步
			\item
			所以可得： \(f[i][j] = f[f[i][j - 1]][j - 1]\)
		\end{itemize}
		
		回到这道题：
		
		暴力的做法即遍历区间 \([l,r]\) ，贪心的让每段的长度尽可能大
		
		考虑用倍增思想优化：
		
		定义 \(f[i][j]\) 表示：
		
		以 \(i\) 为起点，分成 \(2 ^ j\)
		个连续段后，所能到达的最远位置的下一个位置（其中每个段的和都不超过
		\(K\)）
		
		那么不难得到： \(f[i][j] = f[f[i][j - 1]][j - 1]\) （\(f[i][0]\)
		可通过二分前缀和得到
		
		然后对于每个询问 \((L , R)\)：
		
		先判断区间 \([L,R]\) 是否存在 \(A_i\) 使得 \(A_i > K\)
		
		这步我们维护一个权值数组的前缀和 \(O1\) 判断
		
		即当 \(A_i <= K\) 时，\(sum[i] = sum[i - 1]\)
		
		当 \(A_i > K\)时，\(sum[i] = sum[i - 1] + 1\)
		
		当 \(sum[R] - sum[L - 1] > 0\) 则表示该区间存在 \(A_i > K\)，直接输出
		\(Chtholly\)
		
		若 \(sum[R] - sum[L - 1] = 0\) 则从高位往低位枚举 \(j\)：
		
		\begin{quote}
			如果 \(f[L][j] > R\) 则表示从 \(L\) 开始划分出 \(2^j\) 个连续段是 \(OK\)
			的\\
			但是 \(2^j\) 连续段可能太多了（题目要求划分的连续段个数最少\\
			所以就继续往下枚举
		\end{quote}
		
		\begin{quote}
			如果 \(f[L][j] < R\)，则表示从 \(L\) 开始划分出 \(2^j\)
			个连续段是不够的\\
			那就先划分出 \(2^j\) 个连续段，然后再从 \(f[L][j]\) 的位置继续划分\\
			即 \(ans += 1 << j\) ，\(L = f[L][j]\)
		\end{quote}
	\end{quote}
	
	\begin{lstlisting}
		const int N = 1e6 + 10;
		int f[N][22];
		int n , m , k , a[N] , sum[N];
		long long pre[N]; 
		signed main()
		{
			cin >> n >> m >> k;
			for(int i = 1 ; i <= n ; i ++)
			{
				cin >> a[i] , pre[i] = pre[i - 1] + a[i];
				sum[i] = sum[i - 1] + (a[i] > k); 
			}
			for(int j = 0 ; j <= 21 ; j ++) f[n + 1][j] = n + 1;
			
			for(int j = 0 ; j <= 21 ; j ++)
			{
				for(int i = 1 ; i <= n ; i ++)
				{
					f[i][0] = upper_bound(pre + i , pre + 1 + n , k - a[i] + pre[i]) - pre;
					if(!j) continue ;
					f[i][j] = f[f[i][j - 1]][j - 1]; 
				}
			}
			while(m --)
			{
				int l , r , ans = 0;
				cin >> l >> r;
				if(sum[r] - sum[l - 1]) 
				{
					cout << "Chtholly\n";	
					continue ;
				}
				for(int j = 21 ; j >= 0 ; j --)
				{
					if(f[l][j] - 1 < r) 
					{
						ans += 1 << j;
						l = f[l][j];
					}
				}
				cout << ans + 1 << '\n';
			}
			return 0;
		}
	\end{lstlisting}
	
	
\end{document}
